1. Field of the Invention
The present invention relates to a method of encoding an image in the unit of a block of pixels, by dividing image information into plural blocks each consisting of plural pixels, and a method of decoding the encoded data obtained by such encoding, and an apparatus for executing such encoding and decoding.
2. Related Background Art
Since the amount of data encoded from an image is far larger than that of other encoded characters or symbols, there have been proposed various methods for compression, encoding and transmission for facilitating data storage and transmission.
In order to achieve highly advanced compression of continuous tone images or multi-level density images, there has been proposed to encode such images in the unit of a block of pixels, by dividing the image information into plural blocks each consisting of plural pixels.
Particularly in view of data storage, attention is attracted by the method of vector digitizing each image block consisting of plural pixels, as such method is theoretically capable of achieving performance close to the limit of rate distortion.
In such vector digitization, the reproduction vector is designed in advance by a training process with various images, and a reproduction vector, which provides a minimum distortion for the input image at the encoding, is utilized as the code for encoding. Consequently the optimum designing of the reproduction vector is an important factor in the vector digitization. In general, the optimum reproduction vector is determined by a vector digitizing algorithm called LBG method.
This method, however, being based on a principle of minimizing the average distance between the image for training process and the reproduction vector, tends to provide a reproduction vector that is biased by the average images for training process.
Also the vector digitizer is designed with such training process utilizing various images involving different spatial frequency, but, because usual images frequently contain areas of flat density, the image decoded from the encoded signals often shows image quality deterioration in the areas involving high spatial frequency components, such as in the image edges, through such image quality deterioration is less in the areas of flat image density. This is due to a fact that the percentage of edges is less in the training images, and that the amount of information larger in such edge areas than in the areas of flat image density.
Another drawback lies in a fact that the amount of calculation required for designing the digitizer increases logarithmically with the increase of number of order of the vector. Moreover, even if the reproduction vector can be designed, the amount of calculation required for determining a vector of minimum distortion for the input image also increases logarithmically.
Furthermore, the magnitude of the required hardware will be enormous. Particularly the vector digitizing of complete-search type is practically impossible to realize.
The vector digitization can be generalized as dividing a two-dimensional image into blocks, handling the N sample data constituting each block as an N-dimensional Euclidean space R.sup.N, and executing a mapping conversion on R.sup.N for a finite number of subsets. Consequently the number of dimensions of such Euclidean space increases with the number of the sample images, and a corresponding hardware becomes difficult to realize.
For avoiding such drawbacks, it has been tried to incorporate many edges into the training images, or to effect artificial training.
However, the reproduction vector designed in such manner provides an unnatural digitized image.
Though it is also possible to classify the images by their nature and to design the reproduction vector for each class of images, but such method does not provide fundamental solution, because, as already explained above, the amount of information is larger in the edge areas than in the areas of flat image density. Also such method does not throw light in solving the above-mentioned drawbacks relating to the amount of calculation required or the difficulty in realization of hardware.
Furthermore, in the storage or transmission of the data encoded in the unit of block, the image reproduced from such encoded data may be deteriorated due to a distortion in the data resulting from the transmission characteristics of the system.
Furthermore, there may be required various image processings, such as image sharpness enhancement, for the transmitted image.
However the correction for the distortion in the transmission characteristics or the various image processings are sometimes required for the entire image or sometimes for certain frequency components only, and the conventional encoding method has been unable to satisfactorily respond to such requirements.
On the other hand, in such encoding in the unit of a block, the detailed original image is reproduced in the unit of block by an inverse conversion. Consequently such encoding method, in which the image is represented by the entire encoded data, is not suited for a quick-response transmission, such as transmitting a part of the encoded data at first for showing the outline of the entire image and then transmitting the rest of the encoded data for improving the tonal rendition and resolution of the image. Also it is not suited for such transmission as sending detailed data for certain image areas containing denser original information and sending rougher data for the remaining image areas.
For the purpose of improving man-machine interface, there has recently been desired an encoding method capable of sending rough image information at first and progressively improving the resolution with the lapse of time, thereby reproducing the detailed image information, but the conventional encoding methods have been unable to satisfactorily respond to such requirement.
In the conventional data compression encoding methods, the entire image cannot be comprehended until the encoded data of all the plural block constituting an image are decoded.
Consequently, in case of retrieving a desired image from the stored encoded data of plural images, the user cannot identify whether the currently decoded data represent the desired image, until the completion of decoding.